// 1900.[排序]字符排序 https://oj.rnd.huawei.com/problems/1900/details
//给定一个字符串，仅含英文字母和数字，请按如下规则对其进行排序：
//排序后，原位置是数字的，排序后仍然是数字；原位置是字母的，排序后仍然是字母。
//数字：按 0-9 升序。
//英文字母：大写字母大于小写字母，小写字母按 a-z 升序，大写字母按 A-Z 升序。
//输入为一行字符串，长度范围
//[1,1000)，字符串中不会出现除英文字母、数字以外的别的字符。
//输出排序后的字符串。
//输入 a2CB1c
//输出 a1cB2C
//第二、五位置的数字分别为 2、1，排序后为1、2 ；
//第一、三、四、六位置的字母分别为
// a、C、B、c，小写字母a、c排在前；大写字母C、B排在后，并按 A-Z 升序为 B、C ；
//因此最终输出为 a1cB2C
//输入 ab12C4Ac3B
//输出 ab12c3AB4C
// 此题数据量范围较小，可以使用计数排序解决；与一般的计数排序不同的是，
// 由于题目数字和字母相对独立，因此至少需要两个指针分别进行遍历
// （如果将大小写也分开计算的话，则是三个指针）；由于额外空间大小与输入指标无直接关系，
// 因此本方法的时间复杂度为O(n)，空间复杂度为O(1)。

string CharacterSort(const string &inputStr) {
  char num = '0',
       alpha = 'a';  // 定义计数排序数字和字母开始指针，字母指针从 a 开始
  array<wint_t, 128> cts{};  // 定义并初始化字符桶
  string result;
  for (char is : inputStr)  // 将字符装入桶中，并计数
    ++cts[is];
  for (char is : inputStr)
    if (isdigit(is)) {  // 判断是数字的情形
      while (cts[num] == 0)  // 如果该数字已被使用完毕，则找下一个可用的数字
        ++num;
      result += num;
      --cts[num];
    } else {  // 判断是字母的情形
      while (cts[alpha] == 0)  // 如果该字母已被使用完毕，则找下一个可用的字母
        alpha = alpha == 123
                    ? 'A'
                    : alpha + 1;  // 如果该字母已经遍历完 a-z，则从 A 开始
      result += alpha;
      --cts[alpha];
    }
  return result;
}